class Solution {
public:
    bool Find(TreeNode* tree, TreeNode* x)
    {
        if (tree == nullptr)
            return false;
        return tree == x
            || Find(tree->left, x)
            || Find(tree->right, x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;
        if (root == p || root == q)
            return root;

        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;

        if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (pInRight && qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return root;
        }
    }
};
